{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Missing Observations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: missingRolls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出缺失的观测数据"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一份 <code>n + m</code>&nbsp;次投掷单个<strong> 六面</strong> 骰子的观测数据，骰子的每个面从 <code>1</code> 到 <code>6</code> 编号。观测数据中缺失了 <code>n</code> 份，你手上只拿到剩余&nbsp;<code>m</code> 次投掷的数据。幸好你有之前计算过的这 <code>n + m</code> 次投掷数据的 <strong>平均值</strong> 。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>m</code> 的整数数组 <code>rolls</code> ，其中&nbsp;<code>rolls[i]</code> 是第 <code>i</code> 次观测的值。同时给你两个整数 <code>mean</code> 和 <code>n</code> 。</p>\n",
    "\n",
    "<p>返回一个长度为<em> </em><code>n</code><em> </em>的数组，包含所有缺失的观测数据，且满足这<em> </em><code>n + m</code><em> </em>次投掷的 <strong>平均值</strong> 是<em> </em><code>mean</code> 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。</p>\n",
    "\n",
    "<p><code>k</code>&nbsp;个数字的 <strong>平均值</strong> 为这些数字求和后再除以&nbsp;<code>k</code> 。</p>\n",
    "\n",
    "<p>注意 <code>mean</code> 是一个整数，所以 <code>n + m</code> 次投掷的总和需要被&nbsp;<code>n + m</code>&nbsp;整除。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rolls = [3,2,4,3], mean = 4, n = 2\n",
    "<strong>输出：</strong>[6,6]\n",
    "<strong>解释：</strong>所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rolls = [1,5,6], mean = 3, n = 4\n",
    "<strong>输出：</strong>[2,3,2,2]\n",
    "<strong>解释：</strong>所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rolls = [1,2,3,4], mean = 6, n = 4\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>无论丢失的 4 次数据是什么，平均值都不可能是 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rolls = [1], mean = 3, n = 1\n",
    "<strong>输出：</strong>[5]\n",
    "<strong>解释：</strong>所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == rolls.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= rolls[i], mean &lt;= 6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-missing-observations](https://leetcode.cn/problems/find-missing-observations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-missing-observations](https://leetcode.cn/problems/find-missing-observations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,3]\\n4\\n2', '[1,5,6]\\n3\\n4', '[1,2,3,4]\\n6\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        sumform = 0\n",
    "        for x in rolls:\n",
    "            sumform += x\n",
    "        sumforn = (m+n)*mean-sumform\n",
    "        assumen = [6]*n\n",
    "        if sumforn>6*n or sumforn<n:\n",
    "            return []\n",
    "        delta = (6*n - sumforn)//5\n",
    "        left = (6*n - sumforn)%5\n",
    "        for i in range(delta):\n",
    "            assumen[i] = 1\n",
    "        if left>0:\n",
    "            assumen[delta] = 6-left\n",
    "        return assumen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        t = 0\n",
    "        for r in rolls:\n",
    "            t += mean - r\n",
    "        \n",
    "        if t >= 0:\n",
    "            flag = 1\n",
    "        else:\n",
    "            t = -t\n",
    "            flag = -1\n",
    "\n",
    "        ret = [flag * (t // n) + mean] * n\n",
    "        if t % n == 0:\n",
    "            return ret if 1 <= ret[0] <= 6 else []\n",
    "        t = t % n\n",
    "        for i in range(n):\n",
    "            if flag == 1:\n",
    "                if ret[i] != 6:\n",
    "                    x = 6 - ret[i]\n",
    "                    if x >= t:\n",
    "                        ret[i] += t\n",
    "                        t = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        ret[i] = 6\n",
    "                        t -= x\n",
    "            else:\n",
    "                if ret[i] != 1:\n",
    "                    x = ret[i] - 1\n",
    "                    if x >= t:\n",
    "                        ret[i] -= t\n",
    "                        t = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        ret[i] = 1\n",
    "                        t -= x\n",
    "        return ret if t == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        \n",
    "        total = mean * (m + n)\n",
    "        \n",
    "        left = total - sum(rolls)\n",
    "        \n",
    "        # 如果可行，返回任意答案\n",
    "        if left < n: return []\n",
    "        if left > 6 * n: return []\n",
    "        \n",
    "        ans = [1] * n\n",
    "        left -= n\n",
    "        i = 0\n",
    "        while left > 0:\n",
    "            ans[i] += 1\n",
    "            i = (i + 1) % n\n",
    "            left -= 1\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        total_sum = (len(rolls) + n) * mean\n",
    "        missing_sum = total_sum - sum(rolls)\n",
    "        \n",
    "        if missing_sum < n or missing_sum > 6 * n:\n",
    "            return []\n",
    "        \n",
    "        result = [1] * n\n",
    "        missing_sum -= n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while missing_sum > 0 and result[i] < 6:\n",
    "                result[i] += 1\n",
    "                missing_sum -= 1\n",
    "                \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        re = mean * (m + n) - sum(rolls)\n",
    "        if re < n or re > n * 6:\n",
    "            return []\n",
    "        \n",
    "        ans = [1] * n\n",
    "        re -= n\n",
    "        for i in range(n):\n",
    "            if re >= 5:\n",
    "                re -= 5\n",
    "                ans[i] += 5\n",
    "            else:\n",
    "                ans[i] += re\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        res = []\n",
    "        sums = (m+n)*mean\n",
    "        left_sum  = sums-sum(rolls)\n",
    "        if left_sum <= 6*n and left_sum >= n:\n",
    "            left = left_sum // n\n",
    "            p = left_sum % n\n",
    "            res = [left] * n\n",
    "            for i in range(p):\n",
    "                res[i-1] = res[i - 1]+1 \n",
    "            return res\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "\n",
    "        sum1 = sum(rolls)\n",
    "        sumall = mean*(n+len(rolls))\n",
    "        sumnew = sumall-sum1\n",
    "        meannew = sumnew//(n)\n",
    "        res = [meannew for _ in range(n)]\n",
    "        sum_tmp = sum(res)\n",
    "        for i in range(sumnew-sum_tmp):\n",
    "            res[i] += 1\n",
    "        for i in res:\n",
    "            if i>6 or i<=0:\n",
    "                return []\n",
    "        return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        s = mean * (m + n)\n",
    "        rest = s - sum(rolls)\n",
    "        if n <= rest <= 6 * n:\n",
    "            base = rest // n \n",
    "            ans = [base] * n \n",
    "            rest -= base * n \n",
    "            for i in range(rest):\n",
    "                ans[i] += 1\n",
    "            return ans \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        target = (len(rolls) + n) * mean\n",
    "        sum_ = sum(rolls)\n",
    "        diff = target - sum_\n",
    "        if not n <= diff <= n * 6:\n",
    "            return []\n",
    "        ans = [1] * n\n",
    "        diff -= n\n",
    "        for i in range(n):\n",
    "            if diff <= 5:\n",
    "                ans[i] += diff\n",
    "                break\n",
    "            ans[i] += 5\n",
    "            diff -= 5\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        target = (len(rolls) + n) * mean\n",
    "        sum_ = sum(rolls)\n",
    "        diff = target - sum_\n",
    "        if not n <= diff <= n * 6:\n",
    "            return []\n",
    "        ans = [1] * n\n",
    "        diff -= n\n",
    "        for i in range(n):\n",
    "            if diff <= 5:\n",
    "                ans[i] += diff\n",
    "                break\n",
    "            else:\n",
    "                ans[i] += 5\n",
    "                diff -= 5\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        total = mean*(m+n)\n",
    "        rest = total-sum(rolls)\n",
    "        # print(rest)\n",
    "        if rest/n > 6:\n",
    "            return []\n",
    "        elif rest//n == 6:\n",
    "            if rest % n == 0:\n",
    "                return [6]*n\n",
    "            else:\n",
    "                return []\n",
    "        elif rest/n < 1:\n",
    "            return []\n",
    "        else:\n",
    "            num = rest//n\n",
    "            temp = num*n\n",
    "            diff = rest-temp\n",
    "            res = [num]*n\n",
    "            for i in range(diff):\n",
    "                res[i] += 1\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\r\n",
    "        summ = mean * (len(rolls) + n) - sum(rolls)\r\n",
    "        if summ < n or summ > 6 * n:\r\n",
    "            return []\r\n",
    "        res = [1] * n\r\n",
    "        summ -= n\r\n",
    "        for i in range(n):\r\n",
    "            if summ >= 5:\r\n",
    "                res[i] = 6\r\n",
    "                summ -= 5\r\n",
    "            else:\r\n",
    "                res[i] += summ\r\n",
    "                summ = 0\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        tar = mean * (m+n) \n",
    "\n",
    "\n",
    "        diff = tar - sum(rolls)\n",
    "        if diff > n * 6 or diff < n:\n",
    "            return []\n",
    "        if diff % n == 0:\n",
    "            return [diff//n] * n\n",
    "        left = [diff//n] * n\n",
    "        remainder = diff % n\n",
    "        left = [left[i]+1 if i < remainder else left[i] for i in range(n)]\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        def queshilist(queshi, i, n):\n",
    "            for j in range(1, n):\n",
    "                if queshi - q * (n - j) <= 0:\n",
    "                    out.append(q - 1)\n",
    "                    queshi = queshi - q+1\n",
    "                else:\n",
    "                    out.append(q)\n",
    "                    queshi = queshi - q\n",
    "            out.append(queshi)\n",
    "            return out\n",
    "        nums = sum(rolls)\n",
    "        len1 = len(rolls)\n",
    "        queshi = mean * (n + len1) - nums\n",
    "        if queshi < 0:\n",
    "            return []\n",
    "        out = []\n",
    "        if queshi < n:\n",
    "            return []\n",
    "        elif queshi == n:\n",
    "            return [1] * n\n",
    "        elif queshi <= n * 2:\n",
    "            q = 2\n",
    "        elif queshi <= n * 3:\n",
    "            q = 3\n",
    "        elif queshi <= n * 4:\n",
    "            q = 4\n",
    "        elif queshi <= n * 5:\n",
    "            q = 5\n",
    "        elif queshi <= n * 6:\n",
    "            q = 6\n",
    "        else:\n",
    "            return []\n",
    "        if q:\n",
    "            return queshilist(queshi, q, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        def queshilist(queshi, q, n):\n",
    "            queshi1 = queshi - q * n\n",
    "            for i in range(n):\n",
    "                out.append(q)\n",
    "            for i in range(queshi1):\n",
    "                out[i] += 1\n",
    "            return out\n",
    "            # for j in range(1, n):\n",
    "            #     if queshi - q * (n - j) <= 0:\n",
    "            #         out.append(q - 1)\n",
    "            #         queshi = queshi - q+1\n",
    "            #     else:\n",
    "            #         out.append(q)\n",
    "            #         queshi = queshi - q\n",
    "            # out.append(queshi)\n",
    "            # return out\n",
    "        nums = sum(rolls)\n",
    "        len1 = len(rolls)\n",
    "        queshi = mean * (n + len1) - nums\n",
    "        if queshi < 0:\n",
    "            return []\n",
    "        out = []\n",
    "        if queshi < n:\n",
    "            return []\n",
    "        elif queshi == n:\n",
    "            return [1] * n\n",
    "        elif queshi <= n * 2:\n",
    "            q = 1\n",
    "        elif queshi <= n * 3:\n",
    "            q = 2\n",
    "        elif queshi <= n * 4:\n",
    "            q = 3\n",
    "        elif queshi <= n * 5:\n",
    "            q = 4\n",
    "        elif queshi <= n * 6:\n",
    "            q = 5\n",
    "        else:\n",
    "            return []\n",
    "        if q:\n",
    "            return queshilist(queshi, q, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        a = sum(rolls) \n",
    "        b = (n + len(rolls)) * mean - a \n",
    "        if b < n or b > 6 * n:\n",
    "            return []\n",
    "        \n",
    "        x = b // n \n",
    "        r = b % n \n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            if r > 0:\n",
    "                arr.append(x + 1)\n",
    "                r -= 1\n",
    "            else:\n",
    "                arr.append(x)\n",
    "        return arr \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        s = mean * (m + n) - sum(rolls)\n",
    "        ans = []\n",
    "        if s > 6*n or s < n:\n",
    "            return ans\n",
    "        while s > 0 :\n",
    "            temp = math.ceil(s / n)\n",
    "            ans.append(temp)\n",
    "            s -= temp\n",
    "            n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m=len(rolls)\n",
    "        total=(m+n)*mean\n",
    "        mtotal=sum(rolls)\n",
    "        ntotal=total-mtotal\n",
    "\n",
    "        if ntotal<n or ntotal>6*n:\n",
    "            return []\n",
    "        ans=[]\n",
    "        print(ntotal)\n",
    "        while ntotal>0 and n>0:\n",
    "            if ntotal-n>0:\n",
    "                ans.append(min(ntotal-n,5)+1)\n",
    "                ntotal=ntotal-min(ntotal-n,5)-1\n",
    "                \n",
    "                n=n-1\n",
    "            elif ntotal-n==0:\n",
    "                ans.append(1)\n",
    "                ntotal=ntotal-1\n",
    "                n=n-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        l = len(rolls) + n\n",
    "        sum_ = l*mean  - sum(rolls)\n",
    "        if sum_ < n or sum_ > n*6:\n",
    "            return []\n",
    "        x_ = sum_//n\n",
    "        res = [x_ for i in range(n)]\n",
    "        y_ = sum_%n\n",
    "        for i in range(y_):\n",
    "            res[i] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        final_sum = mean * (m + n)\n",
    "        sum_m = sum(rolls)\n",
    "        sum_n = final_sum - sum_m\n",
    "        if sum_n < n or sum_n > 6 * n:\n",
    "            return []\n",
    "        res = []\n",
    "        mean_n = sum_n / n\n",
    "        res.append(int(mean_n))\n",
    "        temp_sum = int(mean_n)\n",
    "        for i in range(1, n):\n",
    "            if temp_sum >= mean_n * i:\n",
    "                res.append(int(mean_n))\n",
    "                temp_sum += int(mean_n)\n",
    "            else:\n",
    "                res.append(int(mean_n) + 1)\n",
    "                temp_sum += (int(mean_n) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        if mean * (len(rolls) + n) - sum(rolls) < n or mean * (len(rolls) + n) - sum(rolls) > 6 * n:\n",
    "            return []\n",
    "        total_num = mean * (n + len(rolls))\n",
    "        last_num = total_num - sum(rolls)\n",
    "        mean_value = last_num / n\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            result.append(int(mean_value))\n",
    "            last_num = last_num - result[-1]\n",
    "            if i != n - 1:\n",
    "                mean_value = last_num / (n - len(result))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        total = (len(rolls) + n) * mean\n",
    "        target = total - sum(rolls)\n",
    "        if target < n or target > 6 * n:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [target]\n",
    "        res = []\n",
    "        avg = target // n\n",
    "        count = target\n",
    "        for i in range(n - 1):\n",
    "            count -= avg\n",
    "            res.append(avg)\n",
    "        index = 0\n",
    "        while count > 6:\n",
    "            res[index] += 1\n",
    "            index += 1\n",
    "            count -= 1\n",
    "        res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        al = mean*(m+n) #总点数\n",
    "        sum_n = al - sum(rolls)\n",
    "        # print(sum_n)  #167\n",
    "        ##现在,有了n次 和 n次的点数和 sum_n,需要安排\n",
    "        ans = []\n",
    "        t = sum_n//n\n",
    "        if sum_n > 6*n or sum_n<n:\n",
    "            return []\n",
    "        # print(t)\n",
    "        t1 = t+1\n",
    "        while t*n < sum_n:\n",
    "            ans += t1,\n",
    "            sum_n -= t1\n",
    "            n -= 1\n",
    "        # print(sum_n, n, ans)\n",
    "\n",
    "        for i in range(n-1):\n",
    "            ans += t,\n",
    "        end = (sum_n-t*(n-1))\n",
    "        ans += end,\n",
    "        return ans if 1<= end <= 6 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        rem = (m+n)*mean-sum(rolls)\n",
    "\n",
    "        # find n integers between 1 and 6 s.t. sum = rem\n",
    "        if rem > n*6 or rem < n:\n",
    "            return []\n",
    "        else:\n",
    "            avg = int(rem/n)\n",
    "            res = [avg for _ in range(n)]\n",
    "            new_rem = rem - n*avg\n",
    "            i = 1\n",
    "            while i <= new_rem:\n",
    "                res[i-1]+=1\n",
    "                i+=1\n",
    "\n",
    "            return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        summ=sum(rolls)\n",
    "        m=len(rolls)\n",
    "        diff=mean*(m+n)-summ\n",
    "        if diff>6*n or diff<n:\n",
    "            return []\n",
    "        res=[]\n",
    "        num=n\n",
    "        while diff>0:\n",
    "            if diff%num!=0:\n",
    "                a=diff//num+1\n",
    "            else:\n",
    "                a=diff//num\n",
    "            diff-=a\n",
    "            num-=1\n",
    "            res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        total = (m + n) * mean\n",
    "        loss = total - sum(rolls)\n",
    "        if loss > 6 * n or loss < n: return []\n",
    "        ans = []\n",
    "        while n > 0:\n",
    "            if loss - 6 >= n:\n",
    "                ans.append(6)\n",
    "                loss -= 6\n",
    "                n -= 1\n",
    "            else:\n",
    "                ans.append(loss - n + 1)\n",
    "                loss -= loss - n + 1\n",
    "                n -= 1\n",
    "                while n > 0:\n",
    "                    ans.append(1)\n",
    "                    loss -= 1\n",
    "                    n -= 1  \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        summ=sum(rolls)\n",
    "        m=len(rolls)\n",
    "        total=mean*(m+n)\n",
    "        if summ+6*n<total or summ+n>total:\n",
    "            return []\n",
    "        news=total-summ\n",
    "        res=[]\n",
    "        num=n\n",
    "        while news>0:\n",
    "            if news%num!=0:\n",
    "                a=news//num+1\n",
    "            else:\n",
    "                a=news//num\n",
    "            news-=a\n",
    "            num-=1\n",
    "            res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        al = mean*(m+n) #总点数\n",
    "        sum_n = al - sum(rolls)\n",
    "        ans = []\n",
    "        if sum_n > 6*n or sum_n<n:  #总判断\n",
    "            return []   ##否则一定能写出解\n",
    "        # t = sum_n//n\n",
    "        # t1 = t+1\n",
    "        # while t*n < sum_n:\n",
    "        #     ans += t1,\n",
    "        #     sum_n -= t1\n",
    "        #     n -= 1\n",
    "        # ans += [t,]*n\n",
    "        # return ans\n",
    "        quotient, remainder = divmod(sum_n, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum1 = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if sum1<=0:\n",
    "            return []\n",
    "        chu = sum1 // n\n",
    "        yu = sum1 % n\n",
    "        return [chu+1]*yu+[chu]*(n-yu) if (chu+1<7 or yu==0) and 0<chu<=6   else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum_n = mean*(len(rolls)+n) - sum(rolls)\n",
    "        if sum_n > 6*n or sum_n<n:    return []   ##否则一定能写出解\n",
    "        q, r = sum_n//n, sum_n%n\n",
    "        return [q + 1] * r + [q] * (n - r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum1 = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if sum1<=0:\n",
    "            return []\n",
    "        chu = sum1 // n\n",
    "        yu = sum1 % n\n",
    "        return [chu+1]*yu+[chu]*(n-yu) if (chu+1<7 or yu==0) and 0<chu<=6   else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        msum = sum(rolls)\n",
    "        nsum = mean*(m+n) - msum\n",
    "        if(nsum < n or nsum > 6*n):\n",
    "            return []\n",
    "        result = []\n",
    "        for d in [6,5,4,3,2]:\n",
    "            maxt = min(n,(nsum-n)//(d-1))\n",
    "            mint = nsum - (d-1)*n \n",
    "            if(mint < 0 or maxt < 0 or maxt < mint):\n",
    "                continue\n",
    "            t = mint\n",
    "            n -= t \n",
    "            nsum -= t*d \n",
    "            result += [d]*t\n",
    "        if(n > 0):\n",
    "            result += [1]*n\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        return [s // n + 1] * (s % n) + [s // n] * (n - s % n) if n <= (s := mean * (len(rolls) + n) - sum(rolls)) <= 6 * n else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        missingSum = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if not n <= missingSum <= n * 6:\n",
    "            return []\n",
    "        quotient, remainder = divmod(missingSum, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        summ=sum(rolls)\n",
    "        m=len(rolls)\n",
    "        diff=mean*(m+n)-summ\n",
    "        if diff>6*n or diff<n:\n",
    "            return []\n",
    "        res=[]\n",
    "        num=n\n",
    "        while diff>0:\n",
    "            if diff%num!=0:\n",
    "                a=diff//num+1\n",
    "                diff-=a\n",
    "                num-=1\n",
    "                res.append(a)\n",
    "            else:\n",
    "                a=diff//num\n",
    "                res+=[a]*num\n",
    "                break\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟构造\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        missingSum = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if not n <= missingSum <= n * 6:\n",
    "            return []\n",
    "\n",
    "        quotient, remainder = divmod(missingSum, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        msum = sum(rolls)\n",
    "        nsum = mean*(m+n) - msum\n",
    "        if(nsum < n or nsum > 6*n):\n",
    "            return []\n",
    "        result = []\n",
    "        for d in [6,5,4,3,2]:\n",
    "            maxt = min(n,(nsum-n)//(d-1))\n",
    "            mint = nsum - (d-1)*n \n",
    "            if(mint < 0 or maxt < 0 or maxt < mint):\n",
    "                continue\n",
    "            t = mint\n",
    "            n -= t \n",
    "            nsum -= t*d \n",
    "            result += [d]*t\n",
    "        if(n > 0):\n",
    "            result += [1]*n\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        a = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if a < n or a > n * 6:\n",
    "            return []\n",
    "        \n",
    "        x, y = divmod(a, n)\n",
    "        return [x] * (n - y) + [x+1] * y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum_n = mean*(n+len(rolls))-sum(rolls)\n",
    "        if not n <= sum_n <= n*6:\n",
    "            return []\n",
    "        quotient, remainder = divmod(sum_n, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum1 = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if sum1<=0:\n",
    "            return []\n",
    "        chu = sum1 // n\n",
    "        yu = sum1 % n\n",
    "        return [chu+1]*yu+[chu]*(n-yu) if (chu+1<7 or yu==0) and 0<chu<=6   else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sum1 = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if sum1<=0:\n",
    "            return []\n",
    "        chu = sum1 // n\n",
    "        yu = sum1 % n\n",
    "        return [chu+1]*yu+[chu]*(n-yu) if (chu+1<7 or yu==0) and 0<chu<=6   else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        res_sum = int((len(rolls) + n) * mean - sum(rolls))\n",
    "        if res_sum > 6 * n:\n",
    "            return []\n",
    "        if res_sum < n:\n",
    "            return []\n",
    "        \n",
    "        points = int(res_sum / n)\n",
    "        res_n = res_sum % n\n",
    "        return [points + 1] * res_n + [points] * (n - res_n)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        m = len(rolls)\n",
    "        msum = sum(rolls)\n",
    "        nsum = mean*(m+n) - msum\n",
    "        if(nsum < n or nsum > 6*n):\n",
    "            return []\n",
    "        result = []\n",
    "        for d in [6,5,4,3,2]:\n",
    "            maxt = min(n,(nsum-n)//(d-1))\n",
    "            mint = nsum - (d-1)*n \n",
    "            if(mint < 0 or maxt < 0 or maxt < mint):\n",
    "                continue\n",
    "            t = mint\n",
    "            n -= t \n",
    "            nsum -= t*d \n",
    "            result += [d]*t\n",
    "        if(n > 0):\n",
    "            result += [1]*n\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        diff = (len(rolls) + n) * mean - sum(rolls)\n",
    "        if not n <= diff <= n * 6:\n",
    "            return []\n",
    "        x, y = divmod(diff, n)\n",
    "        return [x + 1] * y + [x] * (n - y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        count = len(rolls) + n\n",
    "        total = sum(rolls)\n",
    "        expectTotal = mean * count\n",
    "        remain = expectTotal - total\n",
    "\n",
    "        if remain < 1 * n or remain > 6 * n:\n",
    "            return []\n",
    "        ave = remain // n\n",
    "        rest = remain - ave * n\n",
    "        return [ave + 1] * rest + [ave] * (n - rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        sumr = sum(rolls)\n",
    "        target = mean * (len(rolls) + n)\n",
    "        diff = target - sumr\n",
    "        if diff > 6 * n or diff < n:\n",
    "            return []\n",
    "        x = diff % n\n",
    "        return [diff // n] * (n - x) + [diff // n + 1] * x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        missingSum = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if not n <= missingSum <= n * 6:\n",
    "            return []\n",
    "        quotient, remainder = divmod(missingSum, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        total = n * mean + mean * len(rolls) - sum(rolls)\n",
    "        if n <= total <= 6 * n:\n",
    "            d, m = divmod(total, n)\n",
    "            return [d+1] * m + [d] * (n - m)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:\n",
    "        missingSum = mean * (n + len(rolls)) - sum(rolls)\n",
    "        if not n <= missingSum <= n * 6:\n",
    "            return []\n",
    "        quotient, remainder = divmod(missingSum, n)\n",
    "        return [quotient + 1] * remainder + [quotient] * (n - remainder)\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
